//#include <iostream>
//#include <vector>
//#include <unordered_map>
//using namespace std;
//class Solution111 {
//public:
//    static void _sortArray(vector<int>& nums, int key, int left, int right)
//    {
//        if (left >= right)
//            return;
//
//        int i = 0;
//        for (; i < right; )
//        {
//            if (nums[i] == key)
//                i++;
//            else if (nums[i] < key)
//                swap(nums[++left], nums[i++]);
//            else
//                swap(nums[--right], nums[i]);
//        }
//        int random = rand();
//        int keyL = random % (left - 0 + 1) + 0;
//        int keyR = random % (nums.size() - i + 1) + i;
//        _sortArray(nums, nums[keyL], -1, left + 1);
//        _sortArray(nums, nums[keyR], i - 1, nums.size());
//    }
//    static vector<int> sortArray(vector<int>& nums)
//    {
//        srand(time(nullptr));
//        int random = rand();
//        int key = random % nums.size();
//        _sortArray(nums, nums[key], -1, nums.size());
//        return nums;
//    }
//    int getRandom(vector<int>& nums, int left, int right)
//    {
//        int r = rand();
//        return nums[r % (right - left + 1) + left];
//    }
//};
//
//int main1()
//{
//    vector<int> nums = { 5,4,3,2,1 };
//    vector<int> sortarray = Solution::sortArray(nums);
//    for (auto num : sortarray)
//    {
//        cout << num << " ";
//    }
//    cout << endl;
//    return 0;
//}